MRFs model the joint distribution, i.e., p(y,x), over both the observed image data x and the image fragment labels y. However, if the ultimate goal is to obtain the conditional distribution of the image fragment labels given the observed image data, i.e., p(y|x), then conditional random fields (“CRFs”) may model the conditional distribution directly. Conditional on the observed data x, the distribution of the labels y may be described by an undirected graph. From the Hammersley-Clifford Theorem and provided that the conditional probability of the labels y given the observed data x is greater than 0, then the distribution of the posterior probability of the labels given the observed data P(y|x) may factorize according to the following equation:
                              P          ⁢                      (                    ⁢          y          ⁢                                  x            )                          =                              1                          Z              ⁡                              (                x                )                                              ⁢                                    O              ~                        c                    ⁢                                    Y              c                        ⁡                          (                                                y                  c                                ,                x                            )                                                          (        1        )            
The product of the above equation runs over all connected subsets c of nodes in the graph, with corresponding label variables denoted yc associated with observed data denoted x, and a normalization constant denoted Z(x) which is often called the partition function.
Markov random fields (“MRFs”) have been used to model spatial distributions such as those arising in image analysis. For example, patches or fragments of an image may be labeled with a label y based on the observed data x of the patch.